#include <bits/stdc++.h>

using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
		if(!root) return res;
		target = targetSum;
		dfs(*root, 0);
		return res;
	}

private:
	void dfs(TreeNode& root, int val)
	{
		int cur = root.val + val;
		layer.emplace_back(root.val);
		if (!root.left && !root.right && cur == target)
			res.emplace_back(layer);
		else {
			if (root.left)
				dfs(*root.left, cur);
			if (root.right)
				dfs(*root.right, cur);
		}
		layer.pop_back();
	}

	int target;
	vector<int> layer;
	vector<vector<int>> res;
};

int main()
{
	Solution solution;
	return 0;
}
